package com.example.xeldow.osproject;

import android.os.Handler;
import android.support.v7.app.AppCompatActivity;
import android.os.Bundle;
import android.util.Log;
import android.widget.TextView;

import java.lang.reflect.Array;
import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
import java.util.Set;
import java.util.TreeSet;

import javax.security.auth.login.LoginException;

import static java.sql.Types.NULL;

public class MainActivity extends AppCompatActivity {
    private static final String TAG = "MainActivity";
    /**
     * 地址数目
     */
    private static final int ADDRESS_COUNT = 400;
    /**
     * 指令地址
     */
    private int[] mAddress = new int[400];
    /**
     * 用来展示和存放实验数据
     */
    private TextView textView;
    private StringBuilder stringBuilder = new StringBuilder();

    /**
     * 页框
     */
    private int pageFrame;
    /**
     * 命中率
     */
    private double fifo, opt, lru;
    /**
     * 缺页率
     */
    private double losePageFIFO, losePageOPT, losePageLRU;

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);
        textView = findViewById(R.id.text);
        //初始化地址
        initAddress();
        //开始计算
        start();
    }

    /**
     * 生成随机指令地址的函数
     */
    private void initAddress() {
        for (int i = 0; i < ADDRESS_COUNT; i += 4) {
            Random random = new Random();
            int randomAddress;
            /*
            前半段地址
             */
            randomAddress = random.nextInt(200) + 1;
            mAddress[i] = randomAddress;
            mAddress[i + 1] = randomAddress + 1;

            /*
            后半段地址
             */
            randomAddress = random.nextInt(200) + 200;
            //不可以等于399,否则399+1=400
            while (randomAddress == ADDRESS_COUNT-1) {
                randomAddress = random.nextInt(200) + 200;
            }
            mAddress[i + 2] = randomAddress;
            mAddress[i + 3] = randomAddress + 1;
            /*
            打印出地址
             */
//            Log.e(TAG, "initAddress: " + mAddress[i]);
//            Log.e(TAG, "initAddress: " + mAddress[i+1]);
//            Log.e(TAG, "initAddress: " + mAddress[i+2]);
//            Log.e(TAG, "initAddress: " + mAddress[i+3]);
        }

        /*
        转化页地址流数组
         */
        for (int i = 0; i < ADDRESS_COUNT; i++) {
            mAddress[i] = mAddress[i] / 10;
            Log.e(TAG, "initAddress: " + mAddress[i]);
        }

    }

    private void start() {
        for (pageFrame = 4; pageFrame <= 40; pageFrame++) {
            /*
            通过算法计算缺页数
             */
            losePageFIFO = FIFO(pageFrame, mAddress);
            losePageOPT = OPT(pageFrame, mAddress);
            losePageLRU = LRU(pageFrame, mAddress);
            /*
            计算命中率=1-缺页率
             */
            fifo = 1 - losePageFIFO / 400;
            opt = 1 - losePageOPT / 400;
            lru = 1 - losePageLRU / 400;

            //格式化所展示的数据
            DecimalFormat df = new DecimalFormat("#0.0000");
            //记录每次结果并展示在app上
            stringBuilder.append("[" + pageFrame + "]"
                    + "   FIFO:" + df.format(fifo)
                    + "   OPT:" + df.format(opt)
                    + "   LRU:" + df.format(lru));
            stringBuilder.append("\n");
            runOnUiThread(new Runnable() {
                @Override
                public void run() {
                    textView.setText(stringBuilder);
                }
            });
        }
    }


    /**
     * @param x   页框数
     * @param ins 页地址流数组
     * @return 缺页数
     */
    public static int FIFO(int x, int[] ins) {
        int find = 0;
        ArrayList<Integer> FIFOList = new ArrayList<>();
        for (int i = 0; i < ADDRESS_COUNT; i++) {
            /*
            这里与已存在的物理块对比,相同则记一次
             */
            if (FIFOList.contains(ins[i])) {
                find++;
                continue;
            }
            /*
            页框未被填满,直接放入
             */
            if (FIFOList.size() < x) {
                FIFOList.add(ins[i]);
            }
            /*
            把最初放入的移除,最新的填入
             */
            else {
                FIFOList.remove(0);
                FIFOList.add(ins[i]);
            }
        }
        /*
        总访问页面数-不缺页数=却页数
         */
        return ADDRESS_COUNT - find;
    }

    /**
     * @param x   页框数
     * @param ins 页地址流数组
     * @return 缺页数
     */
    public static int OPT(int x, int[] ins) {
        int find = 0;
        ArrayList<Integer> OPTList = new ArrayList<>();
        for (int i = 0; i < ADDRESS_COUNT; i++) {
            //和其他两个算法一样,相同就不发生缺页,不缺页数加一
            if (OPTList.contains(ins[i])) {
                find++;
                continue;
            }
            //物理块未填满,直接放入
            if (OPTList.size() < x) {
                OPTList.add(ins[i]);
            } else {
                ArrayList<Integer> temp = new ArrayList<>();
                int j;
                // 向后查找将用到的元素
                for (j = i + 1; j < ADDRESS_COUNT && temp.size() < x - 1; j++) {
                    //寻找之后的页面队列,只要是和原队列中相同的就现放进去（不重复放置）
                    //由于这个temp容量比OPTList小一,所有没放入的就是最久未访问的
                    if (OPTList.contains(ins[j]) && !temp.contains(ins[j])) {
                        temp.add(ins[j]);
                    }
                }
                // 发现了最不会被用到的元素 或者 没发现但已到末尾
                if (temp.size() == x - 1 || j == ADDRESS_COUNT) {
                    for (int k = 0; k < x; k++) {
                        //如果temp中不存在OPTList中已保存的页面,则视为这个页面以后都不在使用
                        //移除这个页面并填入新页面
                        if (!temp.contains(OPTList.get(k))) {
                            OPTList.remove(k);
                            OPTList.add(ins[i]);
                            break;
                        }
                    }
                }
            }
        }
        return ADDRESS_COUNT - find;
    }


    /**
     * @param x   页框数
     * @param ins 页地址流数组
     * @return 缺页数
     */
    public static int LRU(int x, int[] ins) {
        int find = 0;
        ArrayList<Integer> LRUList = new ArrayList<>();
        for (int i = 0; i < ADDRESS_COUNT; i++) {
            if (LRUList.contains(ins[i])) {
                //找到相同的记一次
                find++;
                //移除物理块中相同的页面
                LRUList.remove((Integer) ins[i]);
                //更新这个页面为最新使用
                LRUList.add(ins[i]);
                continue;
            }
            //物理块没装满直接放入
            if (LRUList.size() < x) {
                LRUList.add(ins[i]);
            }
            //物理块装满,但又是新页面直接装入并移除最旧页面
            else {
                //0位保存着最旧的页面
                LRUList.remove(0);
                LRUList.add(ins[i]);
            }
        }
        return ADDRESS_COUNT - find;
    }

}
